// 真题描述：给定一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

// 给定一个链表: 1->2->3->4->5, 和 n = 2.
// 当删除了倒数第二个结点后，链表变为 1->2->3->5.

/**
 * 快慢指针
 * 一个快指针先走n步 然后慢指针走
 * 快指针走到尾部的时候，慢指针走到  倒数第n个
 */
function ListNode (val) {
    this.val = val || ''
    this.next = null
}

const removeNthFromEnd = function (head, n) {
    // 初始化头节点的前驱节点
    const dummy = new ListNode()
    // dummy 指向头结点
    dummy.next = head
    // 定义快指针和慢指针
    let fast = dummy
    let slow = dummy

    // 快指针先走n
    while(n > 0) {
        fast = fast.next.next
        n--
    }
    // 两个指针同时移动
    while (fast.next) {
        fast = fast.next
        slow = slow.next
    }
    // 删除慢指针后一个结点
    slow.next = slow.next.next
    // 返回头结点
    return dummy.next
}
